import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=17 lang=java
 *
 * [17] 电话号码的字母组合
 */

// @lc code=start
class Solution {
    List<String> res=new ArrayList<>();
    StringBuilder path=new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0){//equals ""也行，但是==不行
            return res;
        }
        String[] map={
            "",//0
            "",//1
            "abc",//2
            "def",//3
            "ghi",//4
            "jkl",//5
            "mno",//6
            "pqrs",//7
            "tuv",//8
            "wxyz"
        };
        dfs(digits, map, 0);
        return res;
    }

    public void dfs(String digits,String[] map,int index){
        if(path.length()==digits.length()){
        //    res.add(new String(path));
           res.add(path.toString());
           return;
        }
        String str=map[digits.charAt(index)-'0'];
        for(int i=0;i<str.length();i++){
            path.append(str.charAt(i));
            dfs(digits, map, index+1);
            path.deleteCharAt(path.length()-1);
        }
    }
}
// @lc code=end

